﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Media.Animation;

namespace wpf_sort_visualization
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {

        private Storyboard storyboard;
        List<int> numbers = new List<int>(10);
        List<TextBlock> tbs = new List<TextBlock>();
        Random random = new Random();
        string[] sortNames = { "选 择 排 序", "插 入 排 序", "冒 泡 排 序", "希 尔 排 序","快 速 排 序", };
        Brush[] color = { Brushes.Red, Brushes.Blue, Brushes.Pink, Brushes.Black, Brushes.Green, 
                          Brushes.Purple, Brushes.Wheat, Brushes.Orange, Brushes.Olive, Brushes.Navy };
        DoubleAnimation da;

        public MainWindow()
        {
            InitializeComponent();
            //this.AnimationPlayer = new AnimationPlayer();
            tbs.AddRange(new TextBlock[] { Number0, Number1, Number2, Number3, Number4, Number5, Number6, Number7, Number8, Number9 });
        }

        private void GenerateButton_Click(object sender, RoutedEventArgs e)
        {
            numbers.Clear();
            for (int i = 0; i < 10; i++)
                numbers.Add(random.Next(1, 99));

            //ASCENDING
            if (ArrangementSelection.Text == "升 序 序 列") { numbers.Sort(); }

            //DESCENDING
            if (ArrangementSelection.Text == "降 序 序 列")
            {
                numbers.Sort();
                numbers.Reverse();
            }

            for (int i = 0; i < numbers.Count; i++)
                tbs[i].Text = numbers[i].ToString();
            ApplySortButton.IsEnabled = true;
        }



        private void Reset()
        {
            int[] values = { 50, 125, 200, 275, 350, 425, 500, 575, 650, 725 };
            string str = "-GENERATE-";
            for (int i = 0; i < tbs.Count; i++)
            {
                tbs[i].BeginAnimation(Canvas.LeftProperty, null);
                tbs[i].BeginAnimation(Canvas.TopProperty, null);
                Canvas.SetLeft(tbs[i], values[i]);
                Canvas.SetTop(tbs[i], 150);
                tbs[i].Text = str[i].ToString();
                tbs[i].Foreground = Brushes.White;
                tbs[i].Background = Brushes.Blue;
            }
            GenerateButton.IsEnabled = true;
        }

        private void ApplySortButton_Click(object sender, RoutedEventArgs e)
        {
            switch (SortingRoutineSelection.Text)
            {
                case "选 择 排 序": InsertionSort(); break;
                case "插 入 排 序": SelectionSort(); break;
                case "冒 泡 排 序": BubbleSort(); break;
                case "希 尔 排 序": ShellSort(); break;
                case "快 速 排 序": QuickSort(0, numbers.Count - 1); break;

            }
        }

        private async void SelectionSort()
        {
            ApplySortButton.IsEnabled = false;
            GenerateButton.IsEnabled = false;

            int current_min, temp;

            for (int i = 0; i < 10; i++)
            {
                current_min = i;

                for (int j = i + 1; j < 10; j++)
                {
                    if (numbers[j] < numbers[current_min])
                    {
                        current_min = j;
                    }
                }

                if (current_min != i)
                {

                    TextBlock curMin = tbs[current_min];
                    TextBlock newMin = tbs[i];

                    moveUp(curMin);
                    moveDown(newMin);
                    await Task.Delay(1000);

                    tbs[i].Background = Brushes.Blue;
                    tbs[current_min].Background = Brushes.Blue;

                    int indexDiff = current_min - i;
                    for (int z = 0; z < indexDiff; z++)
                    {
                        moveLeft(curMin);
                        moveRight(newMin);
                        //curMin.Background = Brushes.Blue;
                        await Task.Delay(1000);

                        tbs[i].Background = Brushes.Blue;
                        tbs[current_min].Background = Brushes.Blue;

                    }
                    tbs[i].Background = Brushes.Blue;
                    tbs[current_min].Background = Brushes.Blue;

                    moveDown(curMin);
                    moveUp(newMin);
                    //curMin.Background = Brushes.Blue;
                    await Task.Delay(1000);

                    tbs[i].Background = Brushes.Blue;
                    tbs[current_min].Background = Brushes.Blue;

                    curMin.Foreground = Brushes.Black;

                    temp = numbers[i];
                    numbers[i] = numbers[current_min];
                    numbers[current_min] = temp;

                    TextBlock tempTB = tbs[i];
                    tbs[i] = tbs[current_min];
                    tbs[current_min] = tempTB;
                }
            }

            MessageBox.Show("单击“确定”重置");
            Reset();
        }

        private async void InsertionSort()
        {
            ApplySortButton.IsEnabled = false;
            GenerateButton.IsEnabled = false;

            for (int i = 1; i < numbers.Count; ++i)
            {
                int key = numbers[i];

                int j = i - 1;

                if (j >= 0 && numbers[j] > key)
                {
                    TextBlock lower = tbs[j + 1];
                    moveDown(lower);
                    await Task.Delay(1000);

                    while (j >= 0 && numbers[j] > key)
                    {
                        TextBlock next = tbs[j];

                        int temp = numbers[j + 1];
                        numbers[j + 1] = numbers[j];
                        numbers[j] = temp;


                        TextBlock tempTB = tbs[j + 1];
                        tbs[j + 1] = tbs[j];
                        tbs[j] = tempTB;

                        tbs[j + 1].Background = Brushes.Blue;
                        tbs[j].Background = Brushes.Blue;

                        moveLeft(lower);
                        moveRight(next);
                        await Task.Delay(1000);

                        tbs[j + 1].Background = Brushes.Blue;
                        tbs[j].Background = Brushes.Blue;


                        j = j - 1;
                    }

                    moveUp(lower);
                    await Task.Delay(1000);

                    tbs[j + 1].Background = Brushes.Blue;
                }

                numbers[j + 1] = key;

            }

            MessageBox.Show("单击“确定”重置");
            Reset();
        }

        private async void BubbleSort()
        {

            for (int i = 0; i <= numbers.Count - 2; i++)
            {
                for (int j = 0; j <= numbers.Count - 2; j++)
                {
                    if (numbers[j] > numbers[j + 1])
                    {
                        moveLeft(tbs[j + 1]);
                        moveRight(tbs[j]);
                        await Task.Delay(1000);

                        tbs[j + 1].Background = Brushes.Blue;
                        tbs[j].Background = Brushes.Blue;

                        int temp = numbers[j + 1];
                        numbers[j + 1] = numbers[j];
                        numbers[j] = temp;

                        TextBlock tempTB = tbs[j + 1];
                        tbs[j + 1] = tbs[j];
                        tbs[j] = tempTB;

                    }
                }
            }
            MessageBox.Show("单击“确定”重置");
            Reset();
        }

        // 将不同分组用不同颜色分开，颜色根据分组数目对应color数组中的颜色
        private async void ShellSort()
        {
            int step = numbers.Count / 2;
            while (step > 0)
            {
                int colori = 0;
                for (int i = 0; i < step; i++)
                {
                    for (int k = i; k < numbers.Count; k += step)
                    {
                        tbs[k].Background = color[colori];
                    }
                    colori++;
                }

                for (int i = step; i < numbers.Count; i++)
                {
                    int j = i;
                    while (j >= step && numbers[j - step] > numbers[j])
                    {
                        moveUp1(tbs[j - step]);
                        moveDown1(tbs[j]);
                        await Task.Delay(1000);

                        moveLeft1(tbs[j], tbs[j - step]);
                        moveRight1(tbs[j - step], tbs[j]);
                        await Task.Delay(1000);

                        moveUp1(tbs[j]);
                        moveDown1(tbs[j - step]);
                        await Task.Delay(1000);

                        int temp = numbers[j];
                        numbers[j] = numbers[j - step];
                        numbers[j - step] = temp;

                        TextBlock tempTB = tbs[j];
                        tbs[j] = tbs[j - step];
                        tbs[j - step] = tempTB;

                        j -= step;

                    }
                }
                step = step / 2;
            }

            MessageBox.Show("单击“确定”重置");
            Reset();
        }

        public void addlog(string log)
        {
            using (StreamWriter tw = new StreamWriter("log.txt",true))
            {
                tw.WriteLine($"{DateTime.Now:yyyy-MM-dd HH:mm:ss} {log}");
            }
        }
        //右移动箭头
        private void moveRightArrow()
        {
            Storyboard storyboard = new Storyboard();
            var left = Canvas.GetLeft(myImage1);
            myImage1.RenderTransform = new TranslateTransform(0, 0);
            DoubleAnimation lefttani = new DoubleAnimation(0, 75, TimeSpan.FromSeconds(1));
            Canvas.SetLeft(myImage1, left + 75);
            storyboard.Children.Add(lefttani);
            Storyboard.SetTarget(lefttani, myImage1);
            lefttani.BeginTime = TimeSpan.FromSeconds(begin);
            Storyboard.SetTargetProperty(lefttani, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.X)"));
            storyboard.Begin();
        }
        //左移动箭头
        private void moveLeftArrow()
        {
            Storyboard storyboard = new Storyboard();
            var right = Canvas.GetLeft(myImage2);
            myImage2.RenderTransform = new TranslateTransform(0, 0);
            DoubleAnimation rightani = new DoubleAnimation(0, -75, TimeSpan.FromSeconds(1));
            Canvas.SetLeft(myImage2, right - 75);
            storyboard.Children.Add(rightani);
            Storyboard.SetTarget(rightani, myImage2);
            rightani.BeginTime = TimeSpan.FromSeconds(begin);
            Storyboard.SetTargetProperty(rightani, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.X)"));
            storyboard.Begin();
        }

        //获取移动矩形的下标
        private int getLeftIndex()
        {
            //获取左右箭头坐标
            int leftArrow = (int)Canvas.GetLeft(myImage1);
            addlog($"340行： leftArrow={leftArrow}");
            //int rightArrow = (int)Canvas.GetLeft(myImage2);
            //计算箭头对应矩形下标,43为起始箭头位置
            int index = (leftArrow - 43) / 75;
            return index;
        }

        private int getRightIndex()
        {
            //获取左右箭头坐标
            int rightArrow = (int)Canvas.GetLeft(myImage2);
            addlog($"351行： rightArrow ={rightArrow}");
            //int rightArrow = (int)Canvas.GetLeft(myImage2);
            //计算箭头对应矩形下标,43为起始箭头位置
            int index = (rightArrow - 43) / 75;
            return index;
        }
        //交换
        private void moveUpRightDown(TextBlock tb)
        {
            //获取左右箭头坐标
            var leftArrow = Canvas.GetLeft(myImage1);
            var rightArrow = Canvas.GetLeft(myImage2);

            // 创建一个TranslateTransform对象并将其吸附到形状
            TranslateTransform translateTransform = new TranslateTransform();
            tb.RenderTransform = translateTransform;
            //定义往上移动动画
            DoubleAnimation up = new DoubleAnimation();
            up.From = 0;
            up.To = -75;
            up.Duration = TimeSpan.FromSeconds(0.3);
            // 添加缓动效果
            up.EasingFunction = new QuadraticEase();

            // 定义往右移动动画
            DoubleAnimation animationX = new DoubleAnimation();
            animationX.From = 0;
            animationX.To = rightArrow - leftArrow;
            animationX.Duration = TimeSpan.FromSeconds(0.3);
            // 添加缓动效果
            animationX.EasingFunction = new QuadraticEase();

            //定义往下移动动画
            DoubleAnimation down = new DoubleAnimation();
            down.From = 0;
            down.To = 75;
            down.Duration = TimeSpan.FromSeconds(0.4);
            // 添加缓动效果
            down.EasingFunction = new QuadraticEase();

            // 创建故事版并将其添加到形状
            Storyboard storyboard = new Storyboard();
            storyboard.Children.Add(animationX);
            storyboard.Children.Add(up);
            storyboard.Children.Add(down);
            // 指定动画目标属性及名字

            Storyboard.SetTarget(up, tb);
            Storyboard.SetTargetProperty(up, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            Storyboard.SetTarget(animationX, tb);
            Storyboard.SetTargetProperty(animationX, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.X)"));
            Storyboard.SetTarget(down, tb);
            Storyboard.SetTargetProperty(down, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            up.BeginTime = TimeSpan.FromSeconds(begin);
            animationX.BeginTime = TimeSpan.FromSeconds(begin + 0.3);
            down.BeginTime = TimeSpan.FromSeconds(begin + 0.6);
            // 开始故事版
            storyboard.Begin();
        }

        private void moveDownLeftUp(TextBlock tb)
        {
            //获取左右箭头坐标
            var leftArrow = Canvas.GetLeft(myImage1);
            var rightArrow = Canvas.GetLeft(myImage2);

            // 创建一个TranslateTransform对象并将其吸附到形状
            TranslateTransform translateTransform = new TranslateTransform();
            tb.RenderTransform = translateTransform;
            //定义往下移动动画
            DoubleAnimation down = new DoubleAnimation();
            down.From = 0;
            down.To = 75;
            down.Duration = TimeSpan.FromSeconds(0.3);
            // 添加缓动效果
            down.EasingFunction = new QuadraticEase();

            // 定义往左移动动画
            DoubleAnimation animationX = new DoubleAnimation();
            animationX.From = 0;
            animationX.To = leftArrow - rightArrow;
            animationX.Duration = TimeSpan.FromSeconds(0.3);
            // 添加缓动效果
            animationX.EasingFunction = new QuadraticEase();

            //定义往上移动动画
            DoubleAnimation up = new DoubleAnimation();
            up.From = 0;
            up.To = -75;
            up.Duration = TimeSpan.FromSeconds(0.6);
            // 添加缓动效果
            up.EasingFunction = new QuadraticEase();

            // 创建故事版并将其添加到形状
            Storyboard storyboard = new Storyboard();
            storyboard.Children.Add(animationX);
            storyboard.Children.Add(down);
            // 指定动画目标属性及名字

            Storyboard.SetTarget(down, tb);
            Storyboard.SetTargetProperty(down, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            Storyboard.SetTarget(animationX, tb);
            Storyboard.SetTargetProperty(animationX, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.X)"));
            Storyboard.SetTarget(up, tb);
            Storyboard.SetTargetProperty(up, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            // 开始故事版
            down.BeginTime = TimeSpan.FromSeconds(begin);
            animationX.BeginTime = TimeSpan.FromSeconds(begin + 0.3);
            up.BeginTime = TimeSpan.FromSeconds(begin + 0.6);
            storyboard.Begin();
        }

        private void moveUpStart(TextBlock tb)
        {
            // 创建一个TranslateTransform对象并将其吸附到形状
            Storyboard storyboard = new Storyboard();
            TranslateTransform translateTransform = new TranslateTransform();
            tb.RenderTransform = translateTransform;
            //定义往上移动动画
            DoubleAnimation startup = new DoubleAnimation();
            startup.From = 0;
            startup.To = -150;
            startup.Duration = TimeSpan.FromSeconds(1);
            // 添加缓动效果
            startup.EasingFunction = new QuadraticEase();
            storyboard.Children.Add(startup);
            Storyboard.SetTarget(startup, tb);
            startup.BeginTime = TimeSpan.FromSeconds(begin);
            Storyboard.SetTargetProperty(startup, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            storyboard.Begin();
        }

        //
        private void moveDownStart(TextBlock tb)
        {
            Storyboard storyboard = new Storyboard();
            // 创建一个TranslateTransform对象并将其吸附到形状
            TranslateTransform translateTransform = new TranslateTransform();
            tb.RenderTransform = translateTransform;
            //定义往上移动动画
            DoubleAnimation animationY = new DoubleAnimation();
            animationY.From = 0;
            animationY.To = 150;
            animationY.Duration = TimeSpan.FromSeconds(1);
            // 添加缓动效果
            animationY.EasingFunction = new QuadraticEase();
            storyboard.Children.Add(animationY);
            Storyboard.SetTarget(animationY, tb);
            animationY.BeginTime = TimeSpan.FromSeconds(begin);
            Storyboard.SetTargetProperty(animationY, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            storyboard.Begin();
        }

        //一轮排序后，start对应的矩形移动到箭头位置
        private void moveRightDown(TextBlock tb)
        {
            //获取左右箭头坐标
            var leftArrow = Canvas.GetLeft(myImage1);
            var rightArrow = Canvas.GetLeft(myImage2);
            // 定义往右移动动画
            DoubleAnimation animationX = new DoubleAnimation();
            animationX.From = 0;
            animationX.To = leftArrow;
            animationX.Duration = TimeSpan.FromSeconds(0.5);
            // 添加缓动效果
            animationX.EasingFunction = new QuadraticEase();

            //定义往下移动动画
            DoubleAnimation down = new DoubleAnimation();
            down.From = 0;
            down.To = 150;
            down.Duration = TimeSpan.FromSeconds(0.5);
            // 添加缓动效果
            down.EasingFunction = new QuadraticEase();

            // 创建故事版并将其添加到形状
            Storyboard storyboard = new Storyboard();
            storyboard.Children.Add(animationX);
            storyboard.Children.Add(down);
            // 指定动画目标属性及名字
            Storyboard.SetTarget(animationX, tb);
            Storyboard.SetTargetProperty(animationX, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.X)"));
            Storyboard.SetTarget(down, tb);
            Storyboard.SetTargetProperty(down, new PropertyPath("(UIElement.RenderTransform).(TranslateTransform.Y)"));
            animationX.BeginTime = TimeSpan.FromSeconds(begin);
            down.BeginTime = TimeSpan.FromSeconds(begin + 0.5);
            // 开始故事版
            storyboard.Begin();
        }
        //begintime的开始时间
        int begin = 0;
        private void QuickSort(int start, int end)
        {
            //设置箭头初始坐标
            // 获取Canvas控件
            Canvas canvas = (Canvas)FindName("canvas");
            // 设置第一个Image控件的left和top属性
            Canvas.SetLeft(myImage1, start);
            Canvas.SetTop(myImage1, 196);
            // 设置第二个Image控件的left和top属性
            Canvas.SetLeft(myImage2, end);
            Canvas.SetTop(myImage2, 196);

            //算法实现
            //获取移动矩形的下标
            int index;
            if (start >= end)
                return;
            int pivot = numbers[start];

            //index = getIndex(leftArrow);
            moveUpStart(tbs[start]);
            begin++;

            int left = start;
            int right = end;
            while (left < right)
            {
                while (numbers[right] >= pivot && left < right)
                {
                    //moveRightArrow(begin);
                    moveLeftArrow();
                    begin++;
                    right = right - 1;
                }
                index = getRightIndex();

                addlog($"575行： index={index}");

                moveDownLeftUp(tbs[index]);
                numbers[left] = numbers[right];
                tbs[left] = tbs[right];
                begin++;
                while (numbers[left] < pivot && left < right)
                {
                    moveRightArrow();
                    begin++;
                    left = left + 1;
                }
                index = getLeftIndex();
                moveUpRightDown(tbs[index]);
                numbers[right] = numbers[left];
                tbs[right] = tbs[left];
                begin++;
            }
            //index = getIndex();
            moveRightDown(tbs[start]);
            begin++;
            numbers[left] = pivot;

            QuickSort(start, left - 1);
            QuickSort(left + 1, end);
        }


        //更改动画
        private void moveUp1(TextBlock tb)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetTop(tb);
            da.To = Canvas.GetTop(tb) - 75;
            da.Duration = new Duration(TimeSpan.FromSeconds(1));

            tb.BeginAnimation(Canvas.TopProperty, da);
            //tb.Background = new SolidColorBrush(Colors.Red);
        }

        private void moveDown1(TextBlock tb)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetTop(tb);
            da.To = Canvas.GetTop(tb) + 75;
            da.Duration = new Duration(TimeSpan.FromSeconds(1));
            //tb.Background = new SolidColorBrush(Colors.Red);
            tb.BeginAnimation(Canvas.TopProperty, da);
            //tb.Background = new SolidColorBrush(Colors.Red);
        }
        private void moveLeft1(TextBlock tb, TextBlock tb2)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetLeft(tb);
            da.By = Canvas.GetLeft(tb2) - Canvas.GetLeft(tb);
            da.Duration = new Duration(TimeSpan.FromSeconds(1));
            //tb.Background = new SolidColorBrush(Colors.Red);
            tb.BeginAnimation(Canvas.LeftProperty, da);
            //tb.Background = new SolidColorBrush(Colors.Red);
        }

        private void moveRight1(TextBlock tb, TextBlock tb2)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetLeft(tb);
            da.By = Canvas.GetLeft(tb2) - Canvas.GetLeft(tb);
            da.Duration = new Duration(TimeSpan.FromSeconds(1));
            //tb.Background = new SolidColorBrush(Colors.Red);
            tb.BeginAnimation(Canvas.LeftProperty, da);
            //tb.Background = new SolidColorBrush(Colors.Red);

        }


        //原版动画
        private void moveUp(TextBlock tb)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetTop(tb);
            da.To = Canvas.GetTop(tb) - 75;
            da.Duration = new Duration(TimeSpan.FromSeconds(1));

            tb.BeginAnimation(Canvas.TopProperty, da);
            tb.Background = new SolidColorBrush(Colors.Red);
        }

        private void moveDown(TextBlock tb)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetTop(tb);
            da.To = Canvas.GetTop(tb) + 75;
            da.Duration = new Duration(TimeSpan.FromSeconds(1));
            //tb.Background = new SolidColorBrush(Colors.Red);
            tb.BeginAnimation(Canvas.TopProperty, da);
            tb.Background = new SolidColorBrush(Colors.Red);
        }
        private void moveLeft(TextBlock tb)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetLeft(tb);
            da.To = Canvas.GetLeft(tb) - 75;
            da.Duration = new Duration(TimeSpan.FromSeconds(1));
            //tb.Background = new SolidColorBrush(Colors.Red);
            tb.BeginAnimation(Canvas.LeftProperty, da);
            tb.Background = new SolidColorBrush(Colors.Red);

        }

        private void moveRight(TextBlock tb)
        {
            da = new DoubleAnimation();
            da.From = Canvas.GetLeft(tb);
            da.To = Canvas.GetLeft(tb) + 75;
            da.Duration = new Duration(TimeSpan.FromSeconds(1));
            //tb.Background = new SolidColorBrush(Colors.Red);
            tb.BeginAnimation(Canvas.LeftProperty, da);
            tb.Background = new SolidColorBrush(Colors.Red);

        }

        private void Stop_Click(object sender, RoutedEventArgs e)
        {
            // 获取DoubleAnimation的Storyboard对象
            //Storyboard storyboard = (Storyboard)da.Parent;
            DoubleAnimation animate = new DoubleAnimation();
            //animate.get
            storyboard = new Storyboard();
        }
    }
}
